package com.vint.leetcode;


/*
 * 1. done
 * 2. easy
 * 3. 最大子序列和
 */
public class Leetcode53 {
	public int maxSubArray(int[] nums) {
		if (nums.length == 0) return 0;
		int max = Integer.MIN_VALUE;
		int tmp = Integer.MIN_VALUE;
		for(int c : nums) {
			if (c > 0) {
				if (tmp > 0) {
					tmp += c;
				} else {
					tmp = c;
				}
			} else {
				if (tmp > 0) {
					tmp += c;
				} else {
					tmp = c;
				}
			}
			if (tmp > max) {
				max = tmp;
			}
		}
		return max;
	}
	public static void main(String[] args) {
		Leetcode53 le = new Leetcode53();
		int[] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 };
		System.out.println(le.maxSubArray(a));
	}
}


